Memory allocation systems assign blocks of memory on request. A memory allocation system employs an allocator to receive relatively large blocks of memory from an operating system and allocate that memory to satisfy memory requests. Upon receipt of a request for a relatively small block of memory, a standard and/or conventional allocator satisfies the request by dividing one of the large blocks of memory into multiple smaller blocks.
A known, standard, and/or conventional memory allocation system is the buddy system. The buddy system divides allocatable blocks of memory into pairs of contiguous equally-sized blocks, for example, buddies. The buddy system employs a buddy system memory allocator that allocates memory blocks of certain permitted sizes. The permitted sizes may be powers of two, such as 4 KB (kilobytes), 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc. In another example, the permitted sizes form a Fibonacci sequence, such as 16 KB, 32 KB, 48 KB, 80 KB, 128 KB, etc. Therefore, each memory block in the buddy system except the smallest allowable memory block can be divided into two smaller blocks of permitted sizes.
The buddy system memory allocator also maintains many free block lists, for example, memory buckets. The buddy system memory allocator maintains one free block list for each of the permitted memory block sizes. Where the permitted memory block sizes are 4 KB, 8 KB, 16 KB, 32 KB, 64 KB, 128 KB, etc., the buddy system memory allocator may maintain a free block list for available 4 KB memory blocks, a free block list for available 8 KB memory blocks, a free block list for available 16 KB memory blocks, a free block list for available 32 KB memory blocks, a free block list for available 64 KB memory blocks, a free block list for available 128 KB memory blocks, etc. The free block lists comprise all the available blocks of a particular size. For example, the free block list for 16 KB memory blocks comprises all of the available 16 KB memory blocks.
When the buddy system memory allocator receives a request for a size of memory, the buddy system memory allocator rounds the requested size up to the size permitted in the buddy system, and returns the first block from the free block list for memory blocks of that permitted size. If the free list for memory blocks of that permitted size is empty, then the buddy system memory allocator splits a larger permitted size memory block and allocates one of the split pieces of memory to satisfy the original memory request. The buddy system memory allocator adds the other split pieces remaining from the satisfied memory request, to the appropriate lists of free blocks of permitted memory sizes in that buddy system.
When memory blocks are released, the buddy system memory allocator may attempt to join, merge, or coalesce two contiguous equally-sized memory blocks or buddies into a single memory block of a larger permitted size. For example, if two 16 KB memory blocks are available and contiguous, the buddy system memory allocator may attempt to coalesce the two 16 KB memory blocks into one 32 KB memory block. The coalescence requires the memory blocks to be contiguous.
In a known, standard, and/or conventional buddy system, the following requirements apply for two blocks of memory to qualify as buddies: 1) the two blocks of memory must be contiguous, 2) the two blocks of memory must be of equal size, and 3) the starting address of the combined block must be aligned to the size of the combined size. For example, if two 16 KB size blocks are to be combined into a 32 KB size, the starting address of the 32 KB size block should at least be 32 KB size aligned; that is, the 32 KB sized block needs to have a starting address that is a multiple of 32 KB to be aligned in the buddy system.